﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0172_SwapPairs : IAlgorithm
    {
        // 24. 两两交换链表中的节点

        // 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

        // 提示：
        //  链表中节点的数目在范围[0, 100] 内
        //  0 <= Node.val <= 100

        public void Test()
        {
            // 算法参数定义
            var head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
            // 算法执行与打印
            var res = SwapPairs(head);
            while (res != null)
            {
                Console.Write(res.val + " ");
                res = res.next;
            }
        }

        // 算法
        //0 1 2 3 4
        //0 2 1 3 4
        public ListNode SwapPairs(ListNode head)
        {
            if (head == null || head.next == null)
                return head;

            var rtnNode = new ListNode(0, head);
            var loopNode = rtnNode;

            while (loopNode.next != null && loopNode.next.next != null)
            {
                var fristNode = loopNode.next;
                var secondNode = loopNode.next.next;
                fristNode.next = secondNode.next;
                loopNode.next = secondNode;
                loopNode.next.next = fristNode;
                loopNode = fristNode;
            }

            return rtnNode.next;
        }
    }
}
